#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/7/23 15:15|15:15
# @Author  : yangdingyi
# @File    : 2020-07-23.64.最小路径和
# @Software: PyCharm
from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        ans = 0
        if not grid:
            return ans
        n = len(grid)
        m = len(grid[0])
        step = [(-1, 0), (0, -1)]
        map = [[-1 for i in range(m)] for j in range(n)]
        map[0][0] = grid[0][0]
        for i in range(n):
            for j in range(m):
                if i or j:
                    for p in step:
                        x, y = i+p[0], j+p[1]
                        if 0 <= x < n and 0 <= y < m:
                            if map[i][j] < 0 or map[x][y] < map[i][j]:
                                map[i][j] = map[x][y]
                    map[i][j] += grid[i][j]

        ans = map[n-1][m-1]
        return ans


solve = Solution()

questions = [
    ([[1, 3, 1], [1, 5, 1], [4, 2, 1]],),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print(solve.minPathSum(q[0]))
